//给定两个数组，编写一个函数来计算它们的交集。 
//
// 
//
// 示例 1： 
//
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2,2]
// 
//
// 示例 2: 
//
// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[4,9] 
//
// 
//
// 说明： 
//
// 
// 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。 
// 我们可以不考虑输出结果的顺序。 
// 
//
// 进阶： 
//
// 
// 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
// 如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 
// 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 
// 
// Related Topics 排序 哈希表 双指针 二分查找 
// 👍 393 👎 0

package com.simon.leetcode.editor.cn;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class IntersectionOfTwoArraysIi_350 {
    public static void main(String[] args) {
        Solution solution = new IntersectionOfTwoArraysIi_350().new Solution();
        int[] n1 = new int[]{1, 2, 2, 1};
        int[] n2 = new int[]{2, 2};
        System.out.println(JSON.toJSONString(solution.intersect(n1,n2)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Map<Integer,Integer> n1Map = new HashMap<>();
            for(int n1 : nums1){
                Integer n1Cnt = n1Map.getOrDefault(n1,0)+1;
                n1Map.put(n1, n1Cnt);
            }
            int sameSize = Math.min(nums1.length, nums2.length);
            int[] sameList = new int[sameSize];
            int index = 0;
            for(int n2: nums2){
                Integer n2Cnt = n1Map.get(n2);
                if(n2Cnt == null || n2Cnt == 0){
                    continue;
                }else{
                    sameList[index++] = n2;
                    n1Map.put(n2,--n2Cnt);
                }
            }
            return Arrays.copyOfRange(sameList,0,index);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}